package leetcode;

import util.LinkList;
import util.ListNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0143.java
 * @Author : WangRuoyu
 * @Date 2023/10/20 21:21
 */

public class Q0143 {
    private ListNode reveseList(ListNode cur, ListNode post) {
        if (post != null) {
            ListNode tmp = post.next;
            post.next = cur;
            return reveseList(post, tmp);
        } else {
            return cur;
        }
    }

    public void reorderList(ListNode head) {
        ListNode p = head;
        ListNode q = head.next;
        while (q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
        }
        ListNode head2 = p.next;
        p.next = null;
        q = reveseList(null, head2);
        p = head;
        while (q != null) {
            ListNode tmp = q.next;
            q.next = p.next;
            p.next = q;
            q = tmp;
            p = p.next.next;
        }
    }

    public static void main(String[] args) {
        ListNode head = LinkList.createList(new int[]{1, 2, 3, 4, 5});
        Q0143 sl = new Q0143();
        sl.reorderList(head);
        LinkList.printList(head);
    }
}